public class test_1 {
    public static int knapsack(int W, int[] weights, int[] values) {
        int n = weights.length;
        int[] dp = new int[W + 1]; // 初始化dp数组，大小为W+1

        for (int i = 0; i < n; i++) { // 遍历每个物品
            for (int j = W; j >= weights[i]; j--) { // 从背包容量W开始向下遍历，避免覆盖之前的解
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 更新dp[j]
            }
        }

        return dp[W]; // 返回最大价值
    }

    public static void main(String[] args) {
        int W = 10;
        int[] weights = {2, 2, 6, 5, 4};
        int[] values = {6, 3, 5, 4, 6};

        int maxValue = knapsack(W, weights, values);
        System.out.println("The maximum value is: " + maxValue);

        // 如果需要知道选择了哪些物品，需要额外的逻辑来追踪
    }
}
